package com.lh.jianzhioffer.专项练习.字符串;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: linghao
 * @since: 2023/2/27
 *
 * 给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
 *
 * 如果 s 中存在多个符合条件的子字符串，返回任意一个。
 *
 * 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量
 *
 */
public class 含有所有字符的最短字符串017 {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC",t="ABC";
        System.out.println(minWindow(s,t));
    }


    public static String minWindow(String s, String t) {
        String ret = "";
        if(s == null || t == null)return ret;
        if(s.equals(t))return t;
        if(s.length() < t.length())return ret;

        Deque<Character> deque = new LinkedList<>();
        int min = 0;
        char[] chars = s.toCharArray();
        for(char c : chars){
            if(t.length() <= deque.size()){
                while (isContains(t,deque)){
                    deque.poll();
                }
                while (isContains(t,deque)){
                    deque.pollLast();
                }
                min = Math.min(min,deque.size());
            }
            deque.add(c);
        }
        return deque.toString();
    }

    private static boolean isContains(String t, Queue<Character> queue) {
        char[] chars = t.toCharArray();
        int count = 0;
        for(char c : chars){
            if(queue.contains(c)){
                count++;
            }
        }
        if(chars.length == count){
            return true;
        }
        return false;
    }
}
